package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 12/9/20 11:34 AM
 *
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
 */
public class _123_买卖股票的最佳时机_III_03 {


    public int maxProfit01(int[] prices) {

        if (prices == null || prices.length <= 1) {

            return 0;
        }

        int s1 = Integer.MIN_VALUE;
        int s2 = 0;
        int s3 = s1;
        int s4 = 0;

        for (int i = 0; i < prices.length; i++) {

            s1 = Math.max(s1,-prices[i]);
            s2 = Math.max(s2,s1 + prices[i]);
            s3 = Math.max(s3,s2 - prices[i]);
            s4 = Math.max(s4,s3 + prices[i]);
        }


        return Math.max(s2,s4);
    }


    public int maxProfit(int[] prices) {

        if (prices == null || prices.length <= 1) {

            return 0;
        }


        /**
         *
         * k 表示天数
         *
         *   S0: 没有购买股票的最大利润
         *      S0 = 0
         *   S1: 购买股票后的最大利润
         *      S1 = max(S1,S0 - prices[k]);
         *   S2: 卖出之前购买的股票的最大利润
         *      S2 = max(S2,S1 + prices[k]);
         *   S3: 购买股票最大利润
         *      S3 = max(S3,S2 - prices[k]);
         *   S4: 卖出股票的最大利润
         *      S4 = max(S3,S3 + prices[k]);
         */

        int len = prices.length;
        int[] s1 = new int[len + 1];
        int[] s2 = new int[s1.length];
        int[] s3 = new int[s1.length];
        int[] s4 = new int[s1.length];

        for (int i = 0; i < s1.length; i++) {

            s1[i] = s3[i] = Integer.MIN_VALUE;
        }


        for (int i = 1; i <= len; i++) {

            s1[i] = Math.max(s1[i - 1],-prices[i - 1]);
            s2[i] = Math.max(s2[i - 1],s1[i - 1] + prices[i - 1]);
            s3[i] = Math.max(s3[i - 1],s2[i - 1] - prices[i - 1]);
            s4[i] = Math.max(s4[i - 1],s3[i - 1] + prices[i - 1]);
        }

        System.out.println(Arrays.toString(s1));
        System.out.println(Arrays.toString(s2));
        System.out.println(Arrays.toString(s3));
        System.out.println(Arrays.toString(s4));

        return Math.max(s2[len],s4[len]);
    }


}
